package com.jxb.sort;

import java.util.Arrays;

/**
 * 快速排序
 * 原理：
 *  1：将原数组以基准数进行分割
 *  2：然后分别将分割后的数组的首位与基准数进行调换位置
 *  3：依次进行下去
 * 逻辑如下：
 *  1：添加一个分区指示器，来分割数组
 *      随机获取一个基准数
 *      将基准数的元素与当前数组的最后一个元素进行互换
 *      遍历原数组
 *          若当前元素小于等于基准数
 *              将分区指示器进行累加
 *              若当前元素再分区指示器的右边时，交换当前元素与分区指示器元素的值
 *  2：递归调用分区指示器前的部分
 *  3：递归调用分区指示器后的部分
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] nums = {5,2,3,1,4,5,6,7,4,2,4,5,2,3,6,7,3,4,6,7,8,9,0,4,5,6,7,8,9,0,5,5};
        System.out.println("排序开始----------------->" + Arrays.toString(nums));
        int[] res = sortArray(nums);
        System.out.println("排序结束----------------->" + Arrays.toString(res));
    }

    public static int[] sortArray(int[] nums) {
        if (nums.length <= 0) {
            return nums;
        }
        return sort(nums,0,nums.length-1);
    }

    private static int[] sort(int[] nums, int start, int end) {
        //将数据分割成2部分，获取分区指示器
        int zoneIndex = partition(nums,start,end);
        if (zoneIndex > start) {
            sort(nums,start,zoneIndex-1);
        }
        if (zoneIndex < end) {
            sort(nums,zoneIndex + 1,end);
        }
        System.out.println("本轮排序后的数组");
        System.out.println(Arrays.toString(nums));
        System.out.println("--------------------");
        return nums;
    }




    public static int partition(int[] array, int start, int end) {
        //只有一个元素时，无需再分区
        if (start == end) {
            return start;
        }
        //随机选取一个基数
        int pivot = (int)(start + Math.random()*(end - start + 1));
        //设置分区指示器，初始值为分区头元素的下标-1
        int zoneIndex = start - 1;
        System.out.println("开始下标："+start+",结束下标:"+end+",基准数下标："
                +pivot+",元素值:"+array[pivot]+"，分区指示器下标："+zoneIndex);
        //TODO 将基准数与分区尾元素交换位置（因为是随机选择的基准数，所以需要与尾元素进行交换）
        swap(array, pivot, end);
        for (int i = start; i<= end; i++) {
            //当前元素小于等于基准数
            if (array[i] <= array[end]) {
                //将分区指示器进行累加
                zoneIndex++;
                //若当前元素在分区指示器元素的右边时，交换当前元素和分区指示器元素
                if (i > zoneIndex) {
                    swap(array,i,zoneIndex);
                }
            }
            System.out.println("分区指示器："+zoneIndex+",遍历指示器:"+i);
        }
        System.out.println("---------------");
        return zoneIndex;
    }

    private static void swap(int[] array, int pivot, int end) {
        int temp = array[pivot];
        array[pivot] = array[end];
        array[end] = temp;
    }

}
